Java重现NEAT Road Network Aware Trajectory Clustering论文实验

发表于   |   分类于   |  

前言

读了一篇基于路网的轨迹挖掘论文，按照老师的要求重现了一下。由于考试周，断断续续写了挺久，现在来总结一下。

正文

匆匆忙忙的进入了研究生阶段的学习，一时间还有些不适应。对研究方向也是从一窍不通到现在能入门了。这是我看的第一篇本方向的论文。我感觉还是很容易明白的。老师叫我看了很久，突然有一天说叫我实验重现一下，我一开始是懵逼的，毕竟这和以前自己写写程序不一样。写的过程还算顺利，虽然遇到很多坑，下面慢慢说。

论文概述

简要的介绍一下论文的大概框架和流程。这篇论文的中心思想是：通过处理大量轨迹，借助路网这一工具进行频繁轨迹的挖掘。下面分三个阶段介绍论文核心算法。

阶段一：形成基本簇

输入：{TR1,TR2,…,TRN} //TR为点轨迹序列的集合
输出：{S0,S1,…,SN} //S为基本簇的集合

左图是一张路网地图，存储形式为图（V，E），图上有N条输入的轨迹。右图显示第一阶段的输出结果：基本簇的集合。那么什么是基本簇呢？可以简单的理解为路网上的每一条路段就是一个簇，N条轨迹被根据路段进行切割，然后合并到对应的路段，形成基本簇的集合。如图，我们可以看到12个基本簇，每个簇上存储了很多的轨迹段，每条边对应的轨迹个数称为这个簇的密度。

难点剖析：

  • 路网匹配问题：目前为止我还没有看更多的算法，所以我采用的是最简单的死办法：遍历。计算每一个轨迹点到每条路线段的最
    短距离，然后判断它属于哪一条路网，也就是哪一个簇。
  • 还是路网的匹配问题，我们知道由于采样率、误差等原因，匹配出来的轨迹肯定是不全的，中间会出现隔断，不能连成一条。一开始我的思路是：若匹配出来的轨迹不是连续的，则对不连续部分，采用匹配最短路径的方式来进行填补，最终形成完整的轨迹段。后来我发现在这么大规模的图上进行最短距离的计算传统的Flord和Dijkstra都不适用，我知道肯定有研究的论文，但是我没那么多时间现学。后来经过和学长的讨论，想到了更好的方法：对于不连续的部分，比如两条边E1和E2，计算他们俩距离最近的点的中点p，接着匹配p属于的边E3，看看E1，E2，E3能否连续。若不能对E1，E3和E2，E3分别再次取中点。这是一个典型的递归。写的过程中我发现各种各样的死循环，最后我考虑设置递归深度最大为4，以来防止死循环，二来我测试了一段数据，递归深度为4匹配后，连通率达到了70%。我觉得可以了，如果再深，时间复杂度将大大提高，程序很慢。

阶段二：形成路径流

输入：{S0,S1,…,SN}
输出：{F0,F1,…,FN} // F={S0，S1，S2…..}F为基本簇的连续集合

在这一阶段，我们将每一个基本簇，通过一定得算法连接起来，从左图的12个基本簇，经过第二阶段，连接成了3个路径流F。
我们默认从密度最高的簇开始扩展。选当前簇的一个顶点，从与它相邻的簇中挑选要扩展的簇，我们考虑以下因素：


说明：

  • 流量：分母为经过当前簇的轨迹个数，分子为同时经过当前簇和待扩展簇的轨迹个数。
  • 密度：分母为当前簇和所有邻居簇的密度的和，分子为待扩展簇的密度。
  • 速度：分母为所有邻居簇的速度和，分子为待扩展簇的速度。

最终我们采用以下公式来挑选待扩展簇：

说明：
我们限定Wq+Wk+Wv=1。例如我们想挑选流量为基础的簇，我们可以设置：Wq=1，Wk=0，Wv=0。以此我们可以调整参数来得到我们想要的结果。直到所有簇被选中或删除，算法结束。

阶段三：路径流优化

输入：{F0,F1,…,FN}
输出：{F0,F1,…,FM}(N>=M)

我们将地理位置上靠得很近的路径流合并成一条，我们考虑两条边四个顶点之间的距离为基础来合并，这就涉及到大规模图上点最短距离的计算。我们知道图上的算法耗时都很高，更不用说这张超大规模图的了。论文采用了Euclidean lower bound (ELB)来减少计算量。 任意两点之间距离肯定大于等于其欧氏距离，先计算欧氏距离，若小于合并要求的最小阈值，则计算图上真实距离，否则直接否弃。

实验

数据源

地图数据：北京市路网地图，格式如下：edges(路段ID，起点ID，终点ID),vertices(点ID，经度，纬度）

轨迹数据：北京市出租车一个月轨迹，格式如下：车辆ID（车辆ID，触发事件，运营状态，GPS时间，GPS经度，GPS纬度，GPS速度，GPS方位，GPS状态）
(PS:老师扔给我的是一个8g的压缩包，解压完55个g我就懵逼了，后来自己写了个提取程序，扔在学长ubuntu的机子上跑了两天解压出来大概11个g，拿回来我又懵逼了，linux和windows换行符不同，所以拿到我电脑上全乱了…..)

算法设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Graph 
{  
	public Graph(String edgeFile, String nodeFile)   // 根据点和边文件初始化路网
	
	//算法第一部分
	public HashMap<Integer, Integer> getBaseCluster(String carID)   //对每一条轨迹进行处理
	{
		for each node in TR:
			getNearEdge(node)   //计算点属于的边
		for each edge in TRList:
			getExtraWay(edge[i],edge[i+1])    //对轨迹段进行补全
	}
	//算法第二部分
	public List<ArrayList> getFlowCluster(int min)
	{
		while ((e = getMaxDensity()) != null) // 获取密度最大的边
		{ 
			new flow;
			flow.add(e);
			extrendFlowCluster(e, e.getStartNode(), flow);   //递归扩展
			extrendFlowCluster(e, e.getEndNode(), flow);
			flowresult.add(flow);
		}
	}
	//算法第三部分
	public List<ArrayList> refineFlowCluster()
	{
		for f2 flow:
			for f2 flow:
				if (isnear(f1,f2)):     //靠近则合并
					f1=f1+f2
					delete f2
	}
}

实验结果

由于我路网服务器还没开始搭建，所以这里做不了可视化分析。而且一开始我采用的单核程序，跑的特别慢，到手的处理结果大概有一百多条处理的轨迹，前几天我把算法改成了多线程的，可是暂时没有服务器能跑的。我用这一百多条轨迹尝试做了轨迹聚类，最后结果还不错看上去。设置密度最低为20，聚出来的路径流长度最高能达到70，长度20以上的路径流有四十多条。好吧，一百多条轨迹实在是太少了，没办法。我现在算法已经改完了，就等放到服务器上去，多跑一点数据出来，这样实验效果能更好。

后记

  1. 看论文的时候觉得条理清晰，因为这篇论文写的也很清楚，层次分明，可是自己做实验才发现很多细节没有考虑过，或者考虑清楚。老师说的先把架构理清楚，数据类型，接口定义好，现在想想还是很有道理的，定好了写起来真的是快。不过我想的不够清楚，到后期还一直在改代码。所以项目有点拖拉。

  2. 对大数据的处理，很多平时写代码不会出现的问题，可是一到处理大数据，就不一样了。就像我开始想的计算最短距离，实现起来才发现不是自己能搞定的。以前写代码不太会考虑时间问题，现在感觉不一样了，算法与算法之间的时间差别真的很大。

附源码地址：https://github.com/xucheng7112/RoadNet （JDK版本为1.8）